package lc.q101_150;

import java.util.*;

/**
 * 最长连续序列
 * 要求复杂度O(n)
 */
public class Q128 {



    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int longestStreak = 0;
        for (int num : nums) {
            if (!set.contains(num - 1)) {
                // 判读num+1
                int currentNum = num;
                int currentStreak = 1;

                while (set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }

    public static void main(String[] args) {
        final Q128 q128 = new Q128();
        System.out.println(q128.longestConsecutive(new int[]{
                -2,-3,-3,7,-3,0,5,0,-8,-4,-1,2
        }));
    }
}
